
//2146.价格范围内最高排名的K样物品
class Solution {
public:
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int tar) {
        //优先级:距离>价格>横坐标>纵坐标
        //因为是距离优先,所以考虑BFS,让距离从小到大一次向外扩展
        int n=grid.size(),m=grid[0].size();
        vector<vector<int>> dxy({{0,1},{0,-1},{1,0},{-1,0}}); 

        vector<vector<int>> ret;  //返回值
        int low=pricing[0],heigh=pricing[1],sx=start[0],sy=start[1];
        queue<pair<int,int>> q;     //队列
        if(grid[sx][sy]>=low&&grid[sx][sy]<=heigh) ret.push_back({sx,sy});  //起点满足条件
        q.push({sx,sy});

        auto comp = [&](vector<int>& v1, vector<int>& v2)
        {
            int a=grid[v1[0]][v1[1]],b=grid[v2[0]][v2[1]];  
            return a < b||a==b&&v1<v2;  //数组也可以进行比较,于字符串比较原理相同
        };

        vector<vector<int>> vist(n,vector<int>(m));   //存储已经到达的位置
        vist[sx][sy]=1;
        while(q.size()&&ret.size()<tar)
        {
            int _size=q.size();
            vector<vector<int>> tmp;  //先使用一个临时数组,存放上下所有满足条件坐标
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dxy[k][0],b=y+dxy[k][1];
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]>=low&&grid[a][b]<=heigh&&!vist[a][b]) tmp.push_back({a,b});
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]&&!vist[a][b]) 
                    {
                        vist[a][b]=1;
                        q.push({a,b});
                    }
                }
            }
            sort(tmp.begin(),tmp.end(),comp);   //对坐标进行排序,因为是在相同距离的坐标,所以只需要考虑234条件即可
            ret.insert(ret.end(),tmp.begin(),tmp.end());
        }  

        if(ret.size()>tar) ret.resize(tar);
        return ret;
    }
};